package tree;

import printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 陈艺博
 * @date 2021-03-03 08:27
 * @description 二叉树
 **/
public class BinaryTree<E> implements BinaryTreeInfo {
    protected int size;
    protected Node<E> root;

    /**
     * 元素的数量
     */
    public int size() {
        return size;
    }

    /**
     * 是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 清空所有元素
     */
    public void clear() {
        root = null;
        size = 0;
    }

    /**
     * 前序遍历
     */
    public void preorderTraversal() {
        preorderTraversal(root);
    }

    private void preorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        System.out.print(node.element + ", ");
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }

    /**
     * 中序遍历
     */
    public void inorderTraversalAsc() {
        inorderTraversalAsc(root);
    }

    private void inorderTraversalAsc(Node<E> node) {
        if (node == null) {
            return;
        }
        inorderTraversalAsc(node.left);
        System.out.println(node.element);
        inorderTraversalAsc(node.right);
    }

    public void inorderTraversalDesc() {
        inorderTraversalDesc(root);
    }

    private void inorderTraversalDesc(Node<E> node) {
        if (node == null) {
            return;
        }
        inorderTraversalDesc(node.right);
        System.out.println(node.element);
        inorderTraversalDesc(node.left);
    }

    /**
     * 后序遍历
     */
    public void postorderTraversal() {
        postorderTraversal(root);
    }

    private void postorderTraversal(Node<E> node) {
        if (node == null) {
            return;
        }
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.println(node.element);
    }

    public void levelOrderTraversal() {
        if (root == null) {
            return;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> head = queue.poll();
            System.out.println(head.element);
            if (head.left != null) {
                queue.offer(head.left);
            }
            if (head.right != null) {
                queue.offer(head.right);
            }

        }
    }

    public void postorder(Visitor<E> visitor) {
        //如果visitor为空不执行
        if (visitor == null) {
            return;
        }
        postorder(root, visitor);
    }

    private void postorder(Node<E> node, Visitor<E> visitor) {
        //如果stop==true 则不执行循环
        if (node == null || visitor.stop) {
            return;
        }

        postorder(node.left, visitor);
        postorder(node.right, visitor);

        // 如果stop==true则不执行visitor.visit逻辑
        if (visitor.stop) {
            return;
        }
        visitor.stop = visitor.visit(node.element);
    }

    public void inorder(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        inorder(root, visitor);
    }

    private void inorder(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) {
            return;
        }
        inorder(node.left, visitor);
        if (visitor.stop) {
            return;
        }
        visitor.stop = visitor.visit(node.element);
        inorder(node.right, visitor);
    }

    public void preorder(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        preorder(root, visitor);
    }

    public void preorder(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) {
            return;
        }
        visitor.stop = visitor.visit(node.element);
        preorder(node.left, visitor);
        preorder(node.right, visitor);
    }

    public void levelOrder(Visitor<E> visitor) {
        if (root == null || visitor == null) {
            return;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> head = queue.poll();
            if (visitor.visit(head.element)) {
                return;
            }
            if (head.left != null) {
                queue.offer(head.left);
            }
            if (head.right != null) {
                queue.offer(head.right);
            }
        }
    }

    /**
     * 自定义访问器
     *
     * @param <E>
     */
    public static abstract class Visitor<E> {
        boolean stop = false;

        abstract boolean visit(E element);
    }

    /**
     * 获取前驱节点
     */
    protected Node<E> predesessor(Node<E> node) {
        if (node == null) {
            return null;
        }
        //前驱节点在左子树当中（node.left.right.right.right......）
        Node<E> p = node.left;
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }

        //从父节点的，祖父节点中找
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

        return node.parent;
    }

    /**
     * 获取后继节点
     */
    protected Node<E> successor(Node<E> node) {
        if (node == null) {
            return null;
        }
        //前驱节点在左子树当中（node.right.left.left.left......）
        Node<E> p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }

        //从父节点的，祖父节点中找
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

        return node.parent;
    }

    /**
     * 递归方法求树高度
     */
    public int height() {
        return height(root);
    }

    private int height(Node<E> node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }

    /**
     * 迭代的方式求树高
     */
    public int height1() {
        int height = 0;
        int levelSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> head = queue.poll();
            levelSize--;

            if (head.left != null) {
                queue.offer(head.left);
            }
            if (head.right != null) {
                queue.offer(head.right);
            }
            if (levelSize == 0) {
                levelSize = queue.size();
                height++;
            }

        }
        return height;
    }

    /**
     * 判断是否为完全二叉树 Complete BinaryTree
     * 完全二叉树： 最后两层才能有叶子节点， 并且最后一层的叶子节点左对齐
     * 逻辑：
     * - 如果树为空，返回false
     * - 如果树不为空，开始层序遍历二叉树（用队列）
     * 1. 如果node.left!=null && node.right!=null, 将left&right放入队列中
     * 2. 如果node.left==null && node.right!=null, 返回false
     * 3. 如果node.left!=null && node.right==null 或者 node.left==null && node.right==null
     * 3.1 该节点以后遍历的节点都为叶子节点， 才是完全二叉树
     * 3.2 否则返回false
     * 3.3 遍历结束返回true
     */
    public boolean isComplete() {
        if (root == null) {
            return false;
        }
        //是否为叶子节点
        boolean leaf = false;
        Queue<Node<E>> queue = new LinkedList<>();

        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            //判断逻辑
            // 3.1
            if (leaf && (!node.isLeaf())) {
                return false;
            }
            // 1
            if (node.isTowChildren()) {
                queue.offer(node.left);
                queue.offer(node.right);
            } else if (node.left == null && node.right != null) {
                // 2
                return false;
            } else {
                // 3
                leaf = true;
                if (node.left != null) {
                    queue.offer(node.left);
                }
            }
        }
        return true;
    }

    /**
     * 判断是否为完全二叉树, 重构 isComplete
     */
    public boolean isComplete1() {
        if (root == null) {
            return false;
        }

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        boolean isLeaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (isLeaf && (!node.isLeaf())) {// 应该是叶子节点， 但是该节点不是叶子节点
                return false;
            }
            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {// node.left == null && node.right != null
                return false;
            }

            if (node.right != null) {
                queue.offer(node.right);
            } else { // node.right == null && node.left ==null 或者 node.right ==null && node.left!=null, 则后边遍历的节点都是叶子节点
                isLeaf = true;
            }
        }
        return true;
    }

    /**
     * 判断元素是否为空
     */
    protected void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }

    protected static class Node<E> {
        E element;
        Node<E> left;//左节点
        Node<E> right;//右节点
        Node<E> parent;//父节点

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        /**
         * 是否是叶子节点
         *
         * @return true 是， false 不是
         */
        public boolean isLeaf() {
            return left == null && right == null;
        }

        /**
         * 节点有两个子节点
         *
         * @return true 是， false否
         */
        public boolean isTowChildren() {
            return left != null && right != null;
        }
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>) node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
        return myNode.element + "_p(" + parentString + ")";
    }
}
